import tree.TreeNode
import java.util.*

/**
 * 镜像二叉树
 *                          1
 *                       /     \
 *                     /         \
 *                    2           7
 *                  / \          / \
 *                 /   \        /   \
 *                3     5      8     9
 *                \    /            / \
 *                4   6           10  11
 *
 *
 */


fun origin(): TreeNode {
    return TreeNode("1",
            TreeNode("2",
                    TreeNode("3",
                            null,
                            TreeNode("4", null, null)),
                    TreeNode("5",
                            TreeNode("6", null, null), null)),
            TreeNode("7",
                    TreeNode("8",
                            null, null),
                    TreeNode("9",
                            TreeNode("10", null, null),
                            TreeNode("11", null, null))))
}


fun main(args: Array<String>) {

    //非递归
    var root = origin()
    mirrorBinaryTreeNonRecursive(root)
    print(root)
}

fun mirrorBinaryTreeNonRecursive(root: TreeNode) {
    val stack = Stack<TreeNode>()
    stack.push(root)
    var node: TreeNode?
    while (stack.size > 0) {
        node = stack.pop()
        val tmp: TreeNode? = node.left
        node.left = node.right
        node.right = tmp
        pushIfNonNull(stack, node.left)
        pushIfNonNull(stack, node.right)
    }
}

fun pushIfNonNull(s: Stack<TreeNode>, n: TreeNode?) {
    if (n != null)
        s.push(n)
}


fun reverseInOrder(root: TreeNode){

}



